class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []

        sort_nums = sorted(nums)
        nums_idx = {}
        for idx in range(0, len(sort_nums)):
            nums_idx[sort_nums[idx]] = idx

        sum_nums = []
        for small_idx in range(0, len(sort_nums)):
            small_value = sort_nums[small_idx]
            if small_value > 0:
                break
            if small_idx > 0 and sort_nums[small_idx - 1] == sort_nums[small_idx]:
                continue

            for mid_idx in range(small_idx + 1, len(sort_nums)):
                if mid_idx > small_idx+1 and sort_nums[mid_idx - 1] == sort_nums[mid_idx]:
                    continue

                mid_value = sort_nums[mid_idx]
                big_value = -(small_value + mid_value)
                if big_value < mid_value:
                    break

                if big_value in nums_idx and nums_idx[big_value] > mid_idx:
                    sum_nums.append([small_value, mid_value, big_value])

        return sum_nums
